package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/09/22 21:32
 **/
class ListNode { int val;
    ListNode next;ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Day20_3_Num109_SortedListToBST {
    class Solution1 {
        public TreeNode sortedListToBST(ListNode head) {
            if(head == null) return null;
            int size = 0;
            ListNode node = head;
            while(node != null) {
                node = node.next;
                size++;
            }
            int[] arr = new int[size];
            int i = 0;
            while(head != null){
                arr[i] = head.val;
                head = head.next;
                i++;
            }
            return dfs(arr, 0, size-1);
        }
        private TreeNode dfs(int[] arr, int l, int r){
            if(l > r) return null;
            int mid = l + ((r-l)>>1);
            TreeNode cur = new TreeNode(arr[mid]);
            cur.left = dfs(arr, l, mid-1);
            cur.right = dfs(arr, mid+1, r);
            return cur;
        }
    }
    class Solution2 {
        public TreeNode sortedListToBST(ListNode head) {
            if(head == null) return null;
            else if(head.next == null) return new TreeNode(head.val);
            ListNode pre = head;
            ListNode cur = pre.next;
            ListNode next = cur.next;
            while(next!=null && next.next!=null){
                pre = pre.next;
                cur = pre.next;
                next = next.next.next;
            }
            pre.next = null;
            TreeNode root = new TreeNode(cur.val);
            root.left = sortedListToBST(head);
            root.right = sortedListToBST(cur.next);
            return root;
        }
    }
}